package 链表;

import java.security.SecureRandom;
import java.util.Deque;
import java.util.LinkedList;

/**
 * @author yzh
 * @version 1.0
 * @date 2022/5/7 23:15
 * 跳表
 * 为单链表逐层建立索引，最后一层的索引个数为 2
 * 查询的时间复杂度: O(logn)
 * 参考：https://baijiahao.baidu.com/s?id=1681318135543891927&wfr=spider&for=pc
 */
public class SkipList<E extends Comparable<? super E>> {
    /**
     * 概率因子
     */
    public static final double UP_RATE = 0.5;
    /**
     * 整个跳表的开始节点
     */
    private Node<E> head;
    /**
     * 保存查询过程中下沉的节点
     */
    private final Deque<Node<E>> stack = new LinkedList<>();
    private final SecureRandom random = new SecureRandom();

    public static class Node<E extends Comparable<? super E>> {
        public E val;
        public Node<E> down, right;

        public Node(E val) {
            this.val = val;
        }
    }

    public SkipList() {
        head = new Node<>(null);
    }

    /**
     * 获取 val 的前节点
     * 1. 从最顶层的索引的头节点开始, 如果当前指向节点的右节点的值小于 val, 则当前节点往前移
     * 2. 如果当前节点的右节点的值大于 val, 则将当前节点移到当前节点的下节点, 将 cur 节点放到 stack 中, 方便添加和删除
     * 3.如果下节点为 null, 则返回当前节点
     *
     * @param val val
     * @return node
     */
    public Node<E> findPredecessor(Object val) {
        stack.clear();
        for (Node<E> cur = head, r = cur.right; ; ) {
            if (r != null) {
                // 如果查找的值大于当前节点右节点值，则继续往右查找
                if (((Comparable) val).compareTo(r.val) > 0) {
                    cur = r;
                    r = r.right;
                    continue;
                }
            }
            // 验证到最底层，返回最底层的节点
            if (cur.down == null) return cur;
            stack.push(cur);
            cur = cur.down;
            r = cur.right;
        }
    }

    /**
     * 查找
     *
     * @param value value
     * @return node
     */
    public Node<E> search(E value) {
        if (value == null) throw new NullPointerException();
        Node preNode = findPredecessor(value);
        // 说明跳表中最大值都小于 value
        if (preNode.right == null) return null;
        if (((Comparable) value).compareTo(preNode.right.val) == 0) return preNode.right;
        return null;
    }

    /**
     * 添加节点
     *
     * @param val value
     */
    public void add(E val) {
        if (val == null) throw new NullPointerException();
        Node<E> preNode = findPredecessor(val);
        // 说明已存在
        if (preNode.right != null && ((Comparable) val).compareTo(preNode.right.val) == 0) return;
        // 将节点加入到底层链表中
        Node<E> node = new Node<>(val);
        node.right = preNode.right;
        preNode.right = node;
        Node<E> up, down;
        for (; ; ) {
            // 对节点进行升级, 根据随机数判断是否升级
            if (random.nextDouble() < UP_RATE) break;
            down = node;
            // 初始化上节点, 并把底层节点加到上节点的 down 属性
            node = new Node<>(val);
            node.down = down;
            // stack 存放查询的时候保存的下沉节点, 如果 stack 为空, 随机升级成功
            // 说明跳表层级往上升一级
            if (stack.isEmpty()) {
                Node newHead = new Node(null);
                // 老头结点作为新节点的的下级节点
                newHead.down = head;
                newHead.right = node;
                head = newHead;
                break;
            }
            // 从 stack 中取出下沉时的节点, 也就是找到了升级节点的前节点
            up = stack.pop();
            node.right = up.right;
            up.right = node;
        }
    }

    /**
     * 删除节点
     *
     * @param val val
     */
    public void delete(E val) {
        if (val == null) throw new NullPointerException();
        Node<E> preNode = findPredecessor(val);
        // 当前层元素不存在
        if (preNode.right != null && val.compareTo(preNode.right.val) != 0) return;
        for (; ; ) {
            if (preNode.right == null || val.compareTo(preNode.right.val) != 0) break;
            // 移除节点
            preNode.right = preNode.right.right;
            // 顶层如果只是 head 节点则要移除顶层节点
            if (head.right == null && head.down != null) head = head.down;
            if (stack.isEmpty()) break;
            preNode = stack.pop();
        }
    }

    /**
     * 遍历
     */
    public void ergodic() {
        for (Node<E> down = head; down != null; down = down.down) {
            Node<E> cur = down;
            while (cur.right != null) {
                System.out.print(cur.right.val + " ");
                cur = cur.right;
            }
            System.out.println();
        }
    }

}
